Project Description

北京大学编译原理课程项目，参照文档https://pku-minic.github.io/online-doc/#/完成

一、编译器概述

1.1 基本功能

本编译器基本具备如下功能：

1. 将SysY语言代码转换至KoopaIR中间表示
2. 将SysY语言代码编译至riscv

二、编译器设计

2.1 主要模块组成

主要由前后端两大部分组成，前端部分代码在ast.cpp中，后端部分代码在visit.cpp中，还有部分辅助函数在utils.cpp中

2.2 主要数据结构

本编译器最核心的数据结构是AST抽象语法树，所有语法单元的AST结构都继承自基类BaseAST

class BaseAST {
 public:
  virtual ~BaseAST() = default;
  
  virtual void Dump() const = 0;
  virtual void *toKoopaIR() const { return nullptr; };
  virtual void *toKoopaIR(std::vector<const void *> &stmts) const { return nullptr; };
  virtual void *toKoopaIR(std::vector<const void *> &stmts, koopa_raw_type_t type) const { return nullptr; };
  virtual void *toKoopaIR(koopa_raw_type_t type) const { return nullptr; };
  virtual void *toKoopaIR(int i) const { return nullptr; };
  virtual void *toKoopaIR(std::vector<const void *> &functions, std::vector<const void *> &values) const { return nullptr; };
  virtual void *toKoopaIR(koopa_raw_type_t type, std::vector<const void *> &values) const { return nullptr; };
  virtual void *toKoopaIR(std::vector<const void *> &init_val_vec, std::vector<int> dim_size) const { return nullptr; };
  virtual int calculate() const { return 0; };
  virtual void *getKoopaIR() const { return nullptr; };
};

主要用于存储语法单元的各种信息，包括type，运算符，次级AST等，具体实现可见ast.h

在if...else...语句方面，由于涉及到二义性问题，所以本编译器采用拆分的方法，将"if..."分离出来

If
  : IF '(' Exp ')' Stmt {
    auto ast = new IfAST();
    ast->exp = unique_ptr<BaseAST>($3);
    ast->stmt = unique_ptr<BaseAST>($5);
    $$ = ast;
  }
  ;

2.3 主要设计考虑及算法选择

2.3.1 符号表的设计考虑

设计了结构体SymbolList管理符号表

class SymbolList {
private:
  std::vector<std::map<std::string, Value>> symbol_list_array;

public:
  ~SymbolList() = default;
  void addSymbol(std::string symbol, Value value);
  Value getSymbol(std::string symbol);
  void newScope();
  void deleteScope();
  void Dump() const;
};

用vector存储不同作用域，每个作用域是一个map，存储ident到Value结构的映射

Value结构体

enum ValueType { Const, Var, Func, Array, Pointer};
struct Value {
  ValueType type;
  union SymbolListValue {
    int const_value;
    koopa_raw_value_t var_value;
    koopa_raw_function_t func_value;
    koopa_raw_value_t array_value;
    koopa_raw_value_t pointer_value;
  } data;
  Value() = default;
  Value(ValueType type, int value);
  Value(ValueType type, koopa_raw_value_t value);
  Value(ValueType type, koopa_raw_function_t value);
};

支持Const, Var, Func, Array, Pointer物种类型，union data中存储实际数据

2.3.2 寄存器分配策略

将所有变量都存在栈上，维护addr_map记录栈中偏移

std::map<koopa_raw_value_t, int> addr_map;